CODE FESTIVAL 2017 qual B C - 3 Steps

解答

code: python

from collections import defaultdict

import sys

sys.setrecursionlimit(100000)

n, m = map(int, input().split())

d = defaultdict(list)

for a, b in ab:

# n個の頂点の色を初期化。0:未着色、1:黒、-1:白

def dfs(v, color):

return False

return False

return True

# 頂点 s と t の間に奇数長のパス（単純パスでなくても良い）が存在したとすると必ず s と t の間に辺が張られる

if dfs(1, 1): # 二部グラフである場合、辺を結ぶことができるのは色が異なる頂点間

black = 0

for i in colors:

if i == 1:

black += 1

white = n - black

# m := すでに結ばれている

print(black*white - m)

else: # 二部グラフでない場合、必ず奇数長のサイクルが存在するので全ての2頂点間のパスの中に奇数長のパスが存在する

# 任意の2頂点間を辺で結ぶ

print(n*(n-1)//2 - m)

テーマ

メモ

提出

code: python

from collections import defaultdict

from collections import deque

n, m = map(int, input().split())

d = defaultdict(list)

for a, b in ab:

# print(d)

que = deque([])

while que:

to, dis = que.popleft()

for t in to:

continue

else:

dis += 1

for idx, v in enumerate(dist):

# print(dist)

# print(d)